package src.CodeTop;

import java.util.PriorityQueue;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 *
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：lists = [[]]
 * 输出：[]
 *
 */

public class _23MergeKSortedLists {
    public static void main(String[] args) {

    }

    public static ListNode mergeKLists(ListNode[] lists) {
        // 定义新链表的头结点
        ListNode newNode = new ListNode(0);
        // 定义遍历指针
        ListNode cur = newNode;
        //    	创建队列
        PriorityQueue<Integer> queue =new PriorityQueue<>();
        // 取出数组中的每一条链表，连接到新链表并存入队列中
        for (ListNode list : lists) {
            // 当该链表不为空
            while (list != null) {
                // 存入队列中
                queue.offer(list.val);
                // 将该结点连接到新链表上
                cur.next = list;
                cur = cur.next;
                list = list.next;
            }
        }
        // 定义修改数值指针
        ListNode modify = newNode.next;
        // 遍历取出优先队列中的值修改链表的值
        while (!queue.isEmpty()) {
            // 获得当前值
            int num = queue.poll();
            modify.val = num;
            modify = modify.next;
        }
        return newNode.next;
    }
}
